<?php class Expression {
	protected $Stack = array ();
	protected $Level = NULL;
	protected $Expect = NULL;
	protected $Table = array (
		'WHITE'               => '(^ \\s+              )x',
		'SUBSTART'            => '(^ \\(               )x',
		'SUBFINISH'           => '(^ \\)               )x',
		'BOOLEAN'             => '(^ ( WIN | FAIL)     )x',
		'INTEGER'             => '(^ [0-9]+            )x',
		'STRING'              => '(^ ( ( \' ) ( .*? ) ( (?<! \' ) ( \' ) ( \' \' )* (?! \' ) ) | ( " ) ( .*? ) ( (?<! " ) ( " ) ( " " )* (?! " ) ) ) )x',
		'COMPOUND'            => '(^ [0-9_a-zA-Z]+ ( \\. [0-9_a-zA-Z] )* )x',
	);
	protected $Priorities = array (
		'power',
		'math-hi',
		'math-lo',
		'minmax',
		'compare',
		'eq',
		'search',
		'stack',
		'logic-and',
		'logic-or',
		'assign',
		'next',
		'lx',
	);
	protected $RevGrammar = array ();




	public function __construct ($Terminators) {
		is_array ($Terminators) or $Terminators = array ($Terminators);
		$this->Table ['TERM'] = '(^ ( '.implode (' | ', array_map ('preg_quote', $Terminators)).' ) )x';
		$NPL = $OpUnary = $OpBinary = array ();
		foreach (get_declared_classes () as $CName) foreach (array ('OpUnary', 'OpBinary') as $OpType) {
			if (in_array ($OpType, class_implements ($CName), TRUE)) {
				$Grammar = call_user_func (array ($CName, 'Grammar'));
				is_array ($Grammar) or $Grammar = array ($Grammar);
				$$OpType = array_merge ($$OpType, $Grammar);
				foreach ($Grammar as $Token) {
					if ('OpBinary' === $OpType) $NPL [$Token] = array_search (call_user_func (array ($CName, 'PriorityClass')), $this->Priorities, TRUE);
					$this->RevGrammar [$Token] = $CName;
				}
			}
		}
		$this->Table ['UNARY'] = '(^ ( '.implode (' | ', array_map ('preg_quote', $OpUnary)).' ) )x';
		$this->Table ['BINARY'] = '(^ ( '.implode (' | ', array_map ('preg_quote', $OpBinary)).' ) )x';
		$this->Priorities = $NPL;
	}

	public function Analyse (&$Stream) {
		$this->Stack = array ();
		$this->Level = NULL;
		$this->SubStart ();
		while (FALSE !== ($Token = $this->Tokenize ($Stream))) {
			switch ($Token ['Type']) {
				case 'NULL':      die ('Unexpected symbol: "'.substr ($Stream, 0, 1)."\", was expecting: {$this->Expect}\n");
				case 'TERM':      break 2;
				case 'WHITE':     break;
				case 'SUBSTART':  $this->SubStart (); break;
				case 'SUBFINISH': $this->FillVacant ($this->SubFinish ()); break;
				case 'BOOLEAN':   $this->AddBoolean ($Token ['Value']); break;
				case 'INTEGER':   $this->AddInteger ($Token ['Value']); break;
				case 'STRING':    $this->AddString ($Token ['Value']); break;
				case 'COMPOUND':  $this->AddCompound ($Token ['Value']); break;
				case 'UNARY':     $this->AddUnary ($this->RevGrammar [$Token ['Value']]); break;
				case 'BINARY':    $this->AddBinary ($this->RevGrammar [$Token ['Value']]); break;
				default:          die ("wait, wat?\n".print_r ($Token, TRUE));
			}
		}
		return ($this->SubFinish ());
	}

#	public function Synthesize ($Tree) {
#		if (is_array ($Tree)) {
#			(array_key_exists (0, $Tree) and array_key_exists (1, $Tree)) or $Tree = array_values ($Tree);
#			if (array_key_exists (2, $Tree)) {
#FIXME associativity
#				is_array ($Tree [1]) and $Tree [1] = call_user_func (array ($this, __FUNCTION__), $Tree [1]);
#				is_array ($Tree [2]) and $Tree [2] = call_user_func (array ($this, __FUNCTION__), $Tree [2]);
#				return (call_user_func (array ($this->RevGrammar [$Tree [0]], 'Operator'), $Tree [1], $Tree [2]));
#			} else {
#				is_array ($Tree [1]) and $Tree [1] = call_user_func (array ($this, __FUNCTION__), $Tree [1]);
#				return (call_user_func (array ($this->RevGrammar [$Tree [0]], 'Operator'), $Tree [1]));
#			}
#		} else return ($Tree);
#	}



	protected function Expect ($What) {
		switch ($What) {
			case 'binary': $this->Expect = 'BINARY,SUBFINISH'; break;
			case 'const': $this->Expect = 'INTEGER,STRING,BOOLEAN,COMPOUND,UNARY,SUBSTART'; break;
		}
	}
	protected function Tokenize (&$Stream) {
		if (strlen ($Stream) < 1) return (FALSE);
		$Result = array ('Type' => 'NULL', 'Value' => '');
		$Matches = array ();
		foreach (explode (',', 'TERM,WHITE,'.$this->Expect) as $Pattern) if (preg_match ($this->Table [$Pattern], $Stream, $Matches)) {
			strlen ($Matches [0]) > strlen ($Result ['Value']) and $Result = array ('Type' => $Pattern, 'Value' => $Matches [0]);
		}
		$Stream = substr ($Stream, strlen ($Result ['Value']));
		return ($Result);
	}


	protected function PriorityCheck ($Op) {
		if (! is_array ($this->Level ['LastBinary'])) return (FALSE);
		$Last = $this->Level ['LastBinary'][0];
		return ($this->Priorities [$Op] < $this->Priorities [$Last]);
	}


	protected function SubStart () {
		unset ($this->Level);
		$this->Level = array ('Vacant' => NULL, 'LastBinary' => NULL);
		$this->Level ['Tree'] = &$this->Level ['Vacant'];
		array_push ($this->Stack, &$this->Level);
		$this->Expect ('const');
	}
	protected function SubFinish () {
		if (count ($this->Stack) < 1) return (FALSE);
		$OldLevel = array_pop ($this->Stack);
		$this->Level = &$this->Stack [count ($this->Stack) - 1];



var_dump ($this->Level);



		$this->Expect ('binary');
		return ($OldLevel ['Tree']);
	}

	protected function FillVacant ($Value) {
		$this->Level ['Vacant'] = $Value;
		unset ($this->Level ['Vacant']);
	}
	protected function AddConst ($Type, $Value) {
		$this->FillVacant (array ($Type, $Value));
		$this->Expect ('binary');
	}
	protected function AddBoolean ($Value) {
		$this->AddConst ('BOOLEAN', $Value);
	}
	protected function AddInteger ($Value) {
		$this->AddConst ('INTEGER', $Value);
	}
	protected function AddString ($Value) {
		$Delim = substr ($Value, 0, 1);
		$Value = substr ($Value, 1, -1);
		$Value = str_replace ("{$Delim}{$Delim}", "$Delim", $Value);
		$this->AddConst ('STRING', $Value);
	}
	protected function AddArray ($Value) {
		$this->AddConst ('ARRAY', $Value);
	}
	protected function AddCompound ($Value) {
		$this->AddUnary ('@'); // FIXME!
		$this->AddString ($Value);
	}
	protected function AddUnary ($Op) {
		$TMP = &$this->Level ['Vacant'];
		unset ($this->Level ['Vacant']);
		$TMP = array ($Op, &$this->Level ['Vacant']);
		unset ($TMP);
		$this->Expect ('const');
	}
	protected function AddBinary ($Op) {
		if ($this->PriorityCheck ($Op)) {
			$TMP = &$this->Level ['LastBinary'][2];
			unset ($this->Level ['LastBinary']);
			$TMP = array ($Op, $TMP, &$this->Level ['Vacant']);
			$this->Level ['LastBinary'] = &$TMP;
			unset ($TMP);
		} else {
			$this->Level ['Tree'] = array ($Op, $this->Level ['Tree'], &$this->Level ['Vacant']);
			$this->Level ['LastBinary'] = &$this->Level ['Tree'];
		}
		$this->Expect ('const');
	}

} ?>